The present technology relates to an information processing apparatus, an information processing method, and a program, and in particular to an information processing apparatus, an information processing method, and a program capable of enhancing the reliability of estimated cause-and-effect relationship among a multiplicity of variables.
Estimation of statistical cause-and-effect relationship from observation data on multivariate random variables according to the related art is roughly divided into a method of obtaining as a score the results of estimation by an information criterion, a maximum likelihood method with penalties, or a Bayesian method and maximizing the score, and a method of estimating the cause-and-effect relationship between variables through a statistical test for the conditional independence between the variables. The resulting cause-and-effect relationship between the variables is often expressed as a graphical model (acyclic model) for good readability of the results.
FIG. 1 shows three examples of a graphical model representing the cause-and-effect relationship between a variable X and a variable Y.
In the graphical model shown in the upper part of FIG. 1, the cause-and-effect relationship between the variable X and the variable Y is unidentified, and the variable X and the variable Y serve as vertexes linked by a non-directional side (undirected edge). In the graphical model shown in the middle part of FIG. 1, the cause-and-effect relationship between the variable X and the variable Y is that the variable X corresponds to the cause and the variable Y corresponds to the effect, and the variable X and the variable Y serve as vertexes linked by a directional side (directed edge) indicating the direction from the cause to the effect. In the graphical model shown in the lower part of FIG. 1, the variable X and the variable Y serve as vertexes lined by three variables and sides that link the variables. In the graphical model shown in the lower part of FIG. 1, the three variables and the sides that link the variables form a path between the variable X and the variable Y, and the path may partially include a directed edge.
The method of estimating the cause-and-effect relationship between variables through a statistical test for the conditional independence between the variables has been rendered important, because the method may possibly estimate the existence of a potential common cause variable and the reason for the direction of a directed edge is based on a physical background. On the other hand, however, the reliability of the estimation results has been low because of an insufficient detection capability of the statistical test.
In an initial attempt of the method, in order to perform a test for the conditional independence between two variables among n-variate random variables, it is considered to extract all combinations of variables, the number of which is 0 at minimum and (n−2) at maximum, from (n−2) variables as a set of condition variables that serve as a condition for the conditional independence, and to perform testing in a round-robin manner. In this case, however, the number of combinations of variables is increased exponentially, and it is not practical to perform calculation using a calculator.
There has later been disclosed an algorithm that significantly reduces the amount of calculation necessary for testing (see P. Spirtes, C. Glymour, R. Scheines, “Causation, Prediction, and Search”, MIT Press, second edition, 2000). If it is assumed that the conditional independence between variables is expressed uniquely by a directed acyclic graph, a set of condition variables that makes two certain variables conditionally independent is determined uniquely, and the condition variables are not conditionally independent of the variable in focus. Under such conditions, testing is performed while increasing the number of the set of condition variables in the ascending order, and a side between the two variables is removed immediately in the case where the independence is not rejected. However, such an algorithm still involves a large number of trials in the test, which may cause frequent test errors.
In order to address such an issue, P. Spirtes et al. also discloses an improvement on the algorithm discussed above that further reduces the amount of calculation on condition that the condition variables are provided on the path between the two variables in focus. During execution of the algorithm, however, sides that are later determined to be independent remain, and it is therefore permitted to follow a long path. Thus, the number of trials in the test may not be effectively significantly reduced.
There is proposed an algorithm that reduces the number of trials of independence tests with a large number of a set of condition variables by recursively dividing the entire graph into small sub-graphs (see R. Yehezkel, B. Lerner, “Bayesian Network Structure Learning by Recursive Autonomy Identification”, Journal of Machine Learning Research, Vol. 10, pp. 1527-1570, 2009). However, the algorithm may not be able to suppress occurrence of a test error that variables that are intrinsically not independent are determined to be independent in an independence test with a small number of a set of condition variables.
Further, X. Xie, Z. Geng, “A Recursive Method for Structural Learning of Directed Acyclic Graphs”, Journal of Machine Learning Research, Vol. 9, pp. 459-483, 2008 discloses performing a recursive process in a method different from the method according to R. Yehezkel et al. In the method according to X. Xie et al., however, a large number of condition variables are necessary for an independence test, which may result in a lack of stability of calculation.